package com.ry.day1129;

import java.util.Arrays;

public class LC125 {
    static class Solution {
        /**
         * @param m: An integer m denotes the size of a backpack
         * @param a: Given n items with size A[i]
         * @param v: Given n items with value V[i]
         * @return: The maximum value
         */
        public int backPackII(int m, int[] a, int[] v) {
           // return shacache(m,a,v);//傻缓存
            return dp(m,a,v); //动态规划
        }

        public int dp(int bag,int[] a,int[] v){
            int n= a.length;
            int[][] dp = new int[n+1][bag+1];

            for (int i = n-1; i >=0 ; i--) {
                for (int rest = 0; rest <=bag ; rest++) {
                    int p1 = dp[i+1][rest];
                    int p2 =0;
                    int next = rest-a[i] <0 ?-1: dp[i+1][rest-a[i]];
                    if(next!=-1){
                        p2 = v[i]+next;
                    }
                    dp[i][rest] = Math.max(p1,p2);
                }
            }

            return dp[0][bag];
        }

        public int shacache(int bag,int[] a,int[] v){
            int n = a.length;
            int[][] dp = new int[n+1][bag+1];
            for (int i = 0; i <=n ; i++) {
                Arrays.fill(dp[i],-1);
            }

            return f1(a,v,0,bag,dp);
        }

        public int f1(int[] a,int[] v,int idx,int rest,int[][] dp){
            if(rest<0) return -1;
            if(idx == a.length) return 0;
            if(dp[idx][rest] !=-1)
                return dp[idx][rest];

            int p1 = f1(a,v,idx+1,rest,dp);
            int p2 =0;
            int next = f1(a,v,idx+1,rest-a[idx],dp);
            if(next!=-1){
                p2=v[idx]+next;
            }
            int ans= Math.max(p1,p2);
            dp[idx][rest] = ans;
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.backPackII(10,new int[]{2,3,5,7},new int[]{1,5,2,4}));
    }

}
